package scene.path 
{
	import event.CommEvent;
	import flash.geom.Point;
	import scene.map.Map;
	import utils.clientConst;
	/**
	 * ...
	 * @author carlor
	 */
	public class PathFinder 
	{
		private var _owner	  : Map;
		private var _cellData : Array;
		private var _uncertainCell: Object;
		private var _colNum   : int;
		
		private var _openList : Object;
		private var _closeList: Object;
	
		private var _fromPos  : Point;
		private var _targetPos: Point;
		private var _camp	  : int;
		
		public function PathFinder(owner: Map) 
		{
			_owner = owner;
			//_cellData = new Array();
			_uncertainCell = new Object();
		}
		
		public function dispose(): void
		{
			_uncertainCell = null;
		}
		
		public function init(cellData: Array): void
		{
			_cellData = cellData;
			_colNum = cellData[0].length;
		}
		
		public function clear(): void
		{
			var key : Object;
			for (key in _openList) {
				if (_openList[key])
					_openList[key].dispose();
				_openList[key] = null;
			}
			_openList = { };
			for (key in _closeList) {
				if (_closeList[key])
					_closeList[key].dispose();;
				_closeList[key] = null;
			}
			_closeList = { };
		}
		
		public function set camp(value: int): void
		{
			_camp = value;
		}
		
		private function getG(x: int, y: int, parentNode: PathNode): int
		{
			if (x == parentNode.x) {
				if (y != parentNode.y)
					return parentNode.g + 10;
				else
					return parentNode.g;
			}else if (y != parentNode.y) {
				return parentNode.g + 14;
			}else {
				return parentNode.g + 10;
			}
		}
		
		private function getH(x: int, y: int, toPos: Point): int
		{
			return (Math.abs(x - toPos.x) + Math.abs(y - toPos.y)) * 10;
		}
		
		private function getV(x: int, y: int, job: int): int
		{
			if (! clientConst.MAPCELL_MOVE[_cellData[y][x]]) return 1;
			if (! clientConst.MAPCELL_MOVE[_cellData[y][x]][job]) return 1;
			if (clientConst.MAPCELL_MOVE[_cellData[y][x]][job] == 1) return 1;
			return Math.round(1 / (1 - clientConst.MAPCELL_MOVE[_cellData[y][x]][job]));
		}
		
		public function getKey(x: int, y: int): int
		{
			return y * _colNum + x;
		}
		
		private function isOverRange(x: int, y: int): Boolean
		{
			return y < 0 || y >= _cellData.length || x < 0 || x >= _cellData[y].length;
		}
		
		private function isBlock(x: int, y: int): Boolean
		{
			return isOverRange(x, y) || _cellData[y][x] == clientConst.MAPCELL_NOMOVE;
		}
		
		private function isUncertain(x: int, y: int): Boolean
		{
			var key: int = getKey(x, y);
			return _uncertainCell[key] != null ? _uncertainCell[key] != _camp : false;
		}
		
		private function inCloseList(x: int, y: int): Boolean
		{
			return _closeList[getKey(x, y)];
		}
		
		private function inOpenList(x: int, y: int): Boolean
		{
			return _openList[getKey(x, y)];
		}
		
		private function sortPath(a: PathNode, b: PathNode): int
		{
			if (a.f > b.f)
				return 1;
			else if (a.f < b.f)
				return -1;
			else {
				if (a.h > b.h)
					return 1
				else
					return -1;
			}
			return 0;
		}
		
		private function find(curNode: PathNode, toPos: Point, job: int, range: int, isMove: Boolean): Boolean
		{
			delete _openList[getKey(curNode.x, curNode.y)];
			_closeList[getKey(curNode.x, curNode.y)] = curNode;
			if (curNode.x == toPos.x && curNode.y == toPos.y) {
				
				return true;
			}
			
			for (var i: int = curNode.y - 1; i <= curNode.y + 1; i++) {
				for (var j: int = curNode.x - 1; j <= curNode.x + 1; j++) {
					if (i != curNode.y && j != curNode.x) continue;
					if (isBlock(j, i)) continue;
					if (isMove && (i != toPos.y || j != toPos.x) && isUncertain(j, i)) continue;
					if  (Math.abs(toPos.x - j) + Math.abs(toPos.y - i) > range) continue;
					if (inCloseList(j, i)) continue;
					
					var gv: int = getG(j, i, curNode);
					var hv: int = getH(j, i, toPos);
					var vv: int = getV(j, i, job);
					var key: int = getKey(j, i);
					var node: PathNode;
					if (inOpenList(j, i)) {
						node = _openList[key];
						if (node.f > gv + hv) {
							_openList[key].setParent(curNode);
							_openList[key].g = getG(j, i, curNode);
						}
					}else {
						node = new PathNode( { x: j, y: i, g: gv, h: hv, v: vv, parent: curNode } );
						if (j == toPos.x && i == toPos.y) {
							_closeList[getKey(j, i)] = node;
							return true;
						}else
							_openList[key] = node;
					}
				}
			}
			var _curNodes: Array = new Array();
			for each (var n: PathNode in _openList) {
				_curNodes.push(n);
			}
			
			//_curNodes.sortOn(["f", "h"]);
			_curNodes.sort(sortPath);
			var result: Boolean;
			for (i = 0; i < _curNodes.length; i++) {
				result = find(_curNodes[i], toPos, job, range, isMove);
				if (result)
					return true;
			}
			
			return false;
		}
		
		public function moveTo(fromPos: Point, toPos: Point, job: int= 1, range: int=300, isMove: Boolean=true): Boolean
		{
			if (isBlock(toPos.x, toPos.y) && (isMove && isUncertain(toPos.x, toPos.y))) return false;
			
			clear();
			var node: PathNode = new PathNode( { x: toPos.x, y: toPos.y, g: 0, h:  getH(fromPos.x, fromPos.y, toPos), v: getV(toPos.x, toPos.y, job)} );;
			_openList[getKey(toPos.x, toPos.y)] = node;
			
			if (find(node, fromPos, job, range, isMove)) {
				_fromPos   = fromPos;
				_targetPos = toPos;
				return true;
			}else
				return false;
		}
		
		public function moveNext(curPos: Point): Point
		{
			if (curPos.x == _targetPos.x && curPos.y == _targetPos.y)
				return null;
			
			var node: PathNode = _closeList[getKey(curPos.x, curPos.y)];
			if (! node || ! node.parent) return null;
			
			return node.parent.pos;
		}
		
		public function addBlock(x: int, y: int, camp: int): void
		{
			if (isOverRange(x, y)) return;
			
			_uncertainCell[getKey(x, y)] = camp;
		}
		
		public function deleteBlock(x: int, y: int): void
		{
			delete _uncertainCell[getKey(x, y)];
		}
		
		private function getDepth(pos: Point): int
		{
			var node: PathNode = _closeList[getKey(pos.x, pos.y)];
			if (! node) return 0;
			if (! node.parent || (pos.x == _targetPos.x && pos.y == _targetPos.y)) return node.v;
			
			return (_fromPos.x == pos.x && _fromPos.y == pos.y) ? getDepth(node.parent.pos) : node.v + getDepth(node.parent.pos);
		}
		///
		public function getRange(pos: Point, job: int, range: int, isMove: Boolean): Array
		{
			var result: Array = new Array();
			for (var i: int = pos.y - range; i <= pos.y + range; i++) {
				for (var j: int = pos.x - range; j <= pos.x + range; j++) {
					var toPos : Point = new Point(j, i);
					if (Math.abs(pos.x - j) + Math.abs(pos.y - i) > range) continue;
					if (j == pos.x && i == pos.y) {
						result.push(toPos);
						continue;
					}	
					if (isBlock(j, i)) continue;
					if (isMove && isUncertain(j, i)) continue;
					
					if (! moveTo(pos, toPos, job, range, isMove)) continue;
					if (getDepth(pos) > range) continue;
					result.push(toPos);
				}
			}
			return result;
		}
		
		public function get targetPos(): Point
		{
			return _targetPos;
		}
	}

}